/**
 * 给定一个包含非负整数的 m x n 网格 grid ，
 *
 * 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 */
public class Test64 {

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid));
    }

    public static int minPathSum(int[][] grid) {

        int rows = grid.length;
        int lines = grid[0].length;
        int[][] minSteps = new int[rows][lines];
        minSteps[0][0] = grid[0][0];

        int row0 = grid[0][0];
        for (int i = 1; i < lines; i++) {
            row0 += grid[0][i];
            minSteps[0][i] = row0;
        }
        int line0 = grid[0][0];
        for (int i = 1; i < rows; i++) {
            line0 += grid[i][0];
            minSteps[i][0] = line0;
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < lines; j++) {
                minSteps[i][j] = Math.min(grid[i][j]+minSteps[i-1][j],grid[i][j]+minSteps[i][j-1]);
            }
        }

        return minSteps[minSteps.length-1][minSteps[0].length-1];
    }
}
